/**
 * Copyright (c) 2010 CCX(China) Co.,Ltd. All Rights Reserved.
 *
 * This software is the confidential and proprietary information of
 * CCX(China) Co.,Ltd. ("Confidential Information").
 * It may not be copied or reproduced in any manner without the express 
 * written permission of CCX(China) Co.,Ltd.
 *
 * Author: Administrator
 * Date: 2010-8-24 上午09:20:38
 */
package com.service;

/**
 * 在序列中查找指定元素，比较多种方法的实现效率
 * 实现方法：普通循环法和二分法
 * 
 * @author Administrator
 * @version 1.0
 * 
 * Modified By：
 * Modified Date：
 * Why & What is modified：
 */
public class DichotomyComment {

	// 在此数字序列中查找指定数字的位置
	int [] iArray = { 1, 5, 9, 14, 27, 39, 41, 50, 62, 222, 345, 612, 981, 1207, 8721 };
	int iSeek = 345; 	// 待寻找的数字
	int iCount = 0; 	// 查找的次数

	/**
	 * 使用普通的循环方法查找指定数字的位置
	 * 
	 * @param anIntVar
	 * @return int 查找次数
	 */
	public int loop(int anIntVar) {
		for (int i = 0; i < iArray.length; i++) {
			iCount++;
			if (anIntVar == iArray[i])
				break;
		}
		
		return iCount;
	}

	/**
	 * 使用二分法查找指定数字的位置
	 * 
	 * @return int 查找次数
	 */
	public int dichotomy() {
		int iIndex = 0; 	// 位置索引
		int iStart = 0; 	// 开始查找的位置
		int iEnd = iArray.length - 1;

		/* 
		 * 定义区间，取区间的中点，
		 * 直到满足精度要求为止
		 */
		while (true) {
			iCount++;
			iIndex = (iStart + iEnd) / 2;
			if (iArray[iIndex] < iSeek) {
				iStart = iIndex;
			} else if (iArray[iIndex] > iSeek) {
				iEnd = iIndex;
			} else {
				break;
			}
		}

		return iCount;
	}
	
	//公用的重要类每次修改须添加以下注释
	//Rewriter：<修改人>
	//Rewrite Date：<修改日期:格式YYYY-MM-DD> 
	//Start1： 
	/* 原代码内容*/ 
	//End1： 
	
	//将原代码内容注释掉，然后添加新代码使用以下注释： 
	//Added by：<修改人>
	//Add date：<添加日期，格式：YYYY-MM-DD> 
	//Start2： 
	//......
	//End2：

	/**
	 * 两种方法的对比实现
	 * 
	 * @param args
	 */
	public static void main(String[] args) {

		DichotomyComment dc = new DichotomyComment();
		DichotomyComment dc1 = new DichotomyComment();

		System.out.println("普通的循环查找，需要比较的次数：\t" + dc.loop(345));
		System.out.println("二分法查找，需要比较的次数：\t" + dc1.dichotomy());
	}

}
